﻿// 0908train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;
/*
给定一些短词字符串作为分割词，去分割一段长字符串。从前往后遍历分割词，查找并分割长字符串为对应的token
分词规则如下:
1.优先匹配最长分割词:若多个分割词可匹配同一位置，选择长度最长的;长度相同时，按字典序较大的优先。
2.未匹配部分保留原样:无法匹配分割词的部分直接作为独立token输出。
3.输出格式:每个token用括号包裹，按原字符串顺序输出。

输入描述:
短词字符串列表，每行一个，空行后输入待分割的长字符串。

输出描述:
括号包裹的分词结果，如(token1)(token2)


示例1:
输入:
zhong guo
zhong
guo
wo
mei guo

wo ai zhong guo mei guo ye xing

输出：
(wo)(ai)(zhong guo)(mei guo)(ye)(xing)
*/
class Solution01
{
public:
    string getToken(vector<string>& cache_vec, string& verify_str)
    {
        string token;
        if (index >= verify_str.size())
        {
            return token;
        }

        for (auto& cache : cache_vec)
        {
            //第一个字符相等
            if (cache[0] == verify_str[index])
            {
                //遍历cache
                bool is_verify = true;
                for (int i = 0; i < cache.size(); i++)
                {
                    if (cache[i] != verify_str[index + i])
                    {
                        is_verify = false;
                    }
                }
                if (is_verify)
                {
                    token = cache;
                    break;
                }
            }
        }
        return token;
        //getToken
    }

    Solution01(vector<string>&cache_vec, string&verify_str)
    {
        //选择长度最长的
        //长度相同时，按字典序较大的优先
        sort(cache_vec.begin(), cache_vec.end(), [](string&a, string&b) {
            if(a.size()==b.size())
            {
                return a > b;
            }
            return a.size() > b.size();
        });

        //跳过前导空白
        while (isspace(verify_str[index]))
        {
            index++;
        }

        vector<string>result;
        while (index<verify_str.size())
        {
            //跳过间隔的空白
            if (isspace(verify_str[index]))
            {
                index++;
                continue;
            }

            string token = getToken(cache_vec, verify_str);
            if (!token.empty())
            {
                result.push_back(token);
                index += token.size();
            }
            else
            {
                //无法匹配 独立输出
                while (index<verify_str.size() &&!isspace(verify_str[index]))
                {
                    token += verify_str[index];
                    index++;
                }
                result.push_back(token);
            }
        }

        for (auto&str:result)
        {
            cout << '(' << str << ')';
        }

        //Solution01
    }
private:
    int index = 0;
};


/*
 现在有 n 个容器服务，服务的启动可能有一定的依赖性（有些服务启动没有依赖），
 其次服务自身启动加载会消耗一些时间。
给你一个 nxn 的二维矩阵 useTime，
其中 useTime[i][i] = 10 表示服务 i 自身启动加载需要消耗 10s，
useTime[i][j] = 1 表示服务 i 启动依赖服务 j 启动完成，useTime[i][k] = 0，
表示服务 i 启动不依赖服务 k。存在0 <= i，j，k < n。
服务之间启动没有循环依赖（不会出现环），
若想对任意一个服务 i 进行集成测试（服务 i 自身也需要加载），
求最少需要等待多少时间

输入描述
第一行输入服务总量 n，之后的 n 行表示服务启动的依赖关系以及自身启动加载耗时
最后输入 k 表示计算需要等待多少时间后可以对服务 k 进行集成测试
其中 1 <= k <= n，1<=n<=100

输出描述
最少需要等待多少时间(s)后可以对服务 k 进行集成测试

输入
3
5 0 0
1 5 0
0 1 5
3
输出
15

服务3 启动依赖服务2，服务 2 启动依赖服务 1，
由于服务 1,2,3 自身加载需要消耗 5s，所以 5+5+5=15，
需等待 15s 后可以对服务 3 进行集成测试
 */
class Solution02
{
public:
    void initMap(vector<vector<int>>& grid)
    {
        for (int r = 0; r < grid_size; r++)
        {
            for (int c = 0; c < grid_size; c++)
            {
                if (r == c)
                {
                    //表示服务 i 自身启动加载
                    value_map[r] = grid[r][c];
                    continue;
                }

                //r!=c
                if (grid[r][c] == 1)
                {
                    //useTime[i][j] = 1 表示服务 i 启动依赖服务 j 启动完成
                    //j->i
                    int start = c, arrive = r;
                    degree_map[start] += 0;
                    degree_map[arrive] += 1;

                    linked_map[start].push_back(arrive);
                    //grid[r][c]==1
                }

            }
        }

        //initMap
    }

    Solution02(vector<vector<int>>&grid, int target_i)
    {
        grid_size = grid.size();
        vector<int>cost_vec(grid_size, 0);

        initMap(grid);
        
        deque<int>bfs_queue;
        //入度为0，入队列
        for (auto&item:degree_map)
        {
	        if (item.second==0)
	        {
                bfs_queue.push_back(item.first);
	        }
        }

        while (!bfs_queue.empty())
        {
	        int top_node = bfs_queue.front();
	        bfs_queue.pop_front();

	        int top_val = value_map[top_node];
	        cost_vec[top_node] += top_val;

	        //降degree
	        if (linked_map.count(top_node)>0)
	        {
	            vector<int>arrive_vec = linked_map.at(top_node);
	            for (auto&child_node:arrive_vec)
	            {
	                degree_map[child_node]--;
                    //top_node是前置依赖服务，比如3依赖1，2，那就要取1，2里时间最长的那个
                    cost_vec[child_node] = max(cost_vec[child_node], cost_vec[top_node]);
	                if (degree_map[child_node]==0)
	                {
	                    bfs_queue.push_back(child_node);
	                }
	            }

			}
        	//while (!bfs_queue.empty())
        }

        //for (auto&num:cost_vec)
        //{
        //    cout << num << ' ';
        //}

        cout << cost_vec[target_i];
        //Solution02
    }
private:
    int grid_size = 0;
    unordered_map<int, int>value_map;
    unordered_map<int, int>degree_map;
    unordered_map<int, vector<int>>linked_map;
};
//服务 3 启动依赖服务 1 和服务 2，服务 4 启动需要依赖服务 1,2,3，
//服务 1,2,3,4 自身加载需要消耗 2s，3s，4s，5s，
//所以 3+4+5=12s（因为服务 1 和服务 2 可以同时启动），需等待 12s 后可以对服务 4 进行集成测试


/*
 M (1 <= M <= 20)辆车需要在一条不能超车的单行道到达终点，起点到终点的距离为N (1 <= N <= 400)
速度快的车追上前车后，只能以前车的速度维续行驶，求最后一车辆到达目的地花费的时间
 注:每辆车固定间隔1小时出发，比如第一辆车0时出发，第二辆车1时出发，依次类推

输入描述
第一行两个数字：M N分别代表车辆数和到终点的距离，以空格分隔。 
接下来M行，每行1个数字 S，代表每辆车的速度。0 < S < 30

输出描述
输出:最后一辆车到达目的地花费的时间

输入
2 11
3
2
输出
5.5
 */
class Solution03
{
public:
    Solution03(vector<double>&num_vec, int distance)
	{
        int v_size = num_vec.size();
        double max_arrive = 0;

        for (int i=0; i<num_vec.size(); i++)
        {
            double curr_arrive = distance / num_vec[i] + i;
            max_arrive = max(max_arrive, curr_arrive);
        }

        double result = max_arrive - (v_size - 1);

        cout << fixed << setprecision(1) << result;
        //Solution03
	}
};


int main()
{
	{
        int v_size, distance;
        cin >> v_size >> distance;

        vector<double>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution03 solu(num_vec, distance);

        return 0;
	}
	{
/*
3
5 0 0
1 5 0
0 1 5
3
*/
        int grid_size;
        cin >> grid_size;
        vector<vector<int>>grid(grid_size, vector<int>(grid_size));

        for (int r=0; r<grid_size; r++)
        {
            for (int c=0; c<grid_size; c++)
            {
                cin >> grid[r][c];
            }
        }
        int target_i;
        cin >> target_i;

        Solution02 solu(grid, target_i-1);
        return 0;
	}
    vector<string>cache_vec;
    string input;
    while (getline(cin, input))
    {
        if (input.empty()) break;
        cache_vec.push_back(input);
    }
    string verify_str;
    getline(cin, verify_str);
    Solution01 solu(cache_vec, verify_str);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
